package 系统复习.回溯算法;


import java.util.*;

/**
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 */
public class L332 {

    // key为起点，value是有序的终点列表
    Map<String, LinkedList<String>> ticketMap = new HashMap<>();
    LinkedList<String> result = new LinkedList<>();
    int total;

    public List<String> findItinerary(List<List<String>> tickets) {
        total = tickets.size() + 1;
        // 初始化ticketMap
        for (List<String> ticket : tickets) {
            addNew(ticket.get(0), ticket.get(1));
        }
        deal("JFK");
        return result;
    }

    boolean deal(String currentLocation) {
        result.add(currentLocation);
        //机票全部用完，找到最小字符路径
        if (result.size() == total) {
            return true;
        }
        //当前位置的终点列表
        LinkedList<String> targetLocations = ticketMap.get(currentLocation);
        //没有从当前位置出发的机票了，说明这条路走不通
        if (targetLocations != null && !targetLocations.isEmpty()) {
            //终点列表中遍历到的终点
            String targetLocation;
            //遍历从当前位置出发的机票
            for (int i = 0; i < targetLocations.size(); i++) {
                targetLocation = targetLocations.get(i);
                //删除终点列表中当前的终点
                targetLocations.remove(i);
                //递归
                if (deal(targetLocation)) {
                    return true;
                }
                //路线走不通，将机票重新加回去
                targetLocations.add(i, targetLocation);
                result.removeLast();
            }
        }
        return false;
    }

    private void addNew(String start, String end) {
        LinkedList<String> startAllEnd = ticketMap.getOrDefault(start, new LinkedList<>());
        if (!startAllEnd.isEmpty()) {
            for (int i = 0; i < startAllEnd.size(); i++) {
                if (end.compareTo(startAllEnd.get(i)) < 0) {
                    startAllEnd.add(i, end);
                }
            }
            startAllEnd.add(startAllEnd.size(), end);
        } else {
            startAllEnd.add(end);
            ticketMap.put(start, startAllEnd);
        }
    }

    public static void main(String[] args) {

        L332 l332 = new L332();
        List<List<String>> list = new ArrayList<>();
        List<String> str1 = new ArrayList<>();
        str1.add("MUC");
        str1.add("LHR");
        list.add(str1);
        List<String> str2 = new ArrayList<>();
        str2.add("JFK");
        str2.add("MUC");
        list.add(str2);
        List<String> str3 = new ArrayList<>();
        str3.add("SFO");
        str3.add("SJC");
        list.add(str3);
        List<String> str4 = new ArrayList<>();
        str4.add("LHR");
        str4.add("SFO");
        list.add(str4);
        List<String> itinerary = l332.findItinerary(list);
        itinerary.forEach(System.out::println);


    }
}
